TCAMs are typically used in routers and Ethernet switches for Internet protocol (IP) address forwarding. The storage elements are typically designed using a dynamic NOR/NAND type cell.
Content addressable memory (CAM) supports a read operation, write operation, and compare operation. A compare bus of the same width (e.g., bits per word) as an entry in the CAM is input at a clock edge. The data of the compare bus is simultaneously compared to every entry in the CAM. That is, the comparison occurs parallel so the bus may be compared to every entry in the CAM during one clock cycle. An entry is a match when every bit in an entry matches the corresponding bit in the compare bus. Alternatively, an entry is a mismatch when any bit in an entry does not match the corresponding bit in the compare bus. The bits of the entries in the CAM are either 0 or 1.
A TCAM is similar to CAM with the addition of a mask value that may be stored in a cell. The mask value may be referred to as a local mask. A mask value is not compared with a compare bit, and therefore, the compare result will always be a match.
FIG. 1 illustrates an architecture of a conventional TCAM 100. As illustrated in FIG. 1, a search word, such as “1101,” is input to a register 150 of the TCAM 100. The search word is compared to the value stored in the TCAM cells 110. TCAMs typically have sixteen TCAM cells per stage. The search is simultaneously conducted across the TCAM cells 110. The content of the TCAM cells 110 may be a high bit (1), a low bit (0), or a mask value (X). Prior to the search, a match line 130-136 for each set of TCAM cells 120-126 is set to high. The match lines 130-136 are input to a priority encoder 140. The TCAM 100 outputs (MLout) the address of the set of TCAM cells that match the search word line. Because the search is a parallel search, the search may be completed in one clock cycle. It should be noted that a mask value may be a 0 or 1, still, in the present disclosure, the mask value may be referred to as an X.
As an example, as illustrated in FIG. 1, a first set of TCAM cells 120 is set to “1 X 0 1,” a second set of TCAM cells 122 is set to “1 0 X 1,” a third set of TCAM cells 124 is set to “1 1 X X,” and a fourth set of TCAM cells 126 is set to “1 X 1 X.” When comparing the content of the TCAM cells to the search bit, when the content of the TCAM cell is a mask value X, the comparison will yield a match. Thus, according to the example illustrated in FIG. 1, the first set of TCAM cells 120 and the third set of TCAM cells 124 match the search word in the register 150. Accordingly, the match lines 130 134 of the first set of TCAM cells 120 and the third set of TCAM cells 124 will indicate a match and the priority encoder 140 outputs the address of the first set of TCAM cells 120 and the third set of TCAM cells 124.
The conventional TCAM architecture is a dynamic circuit and has a high dynamic power dissipation. In some cases, the TCAM may have a dynamic NAND architecture. In other cases, the TCAM may have a dynamic NOR architecture.
In a dynamic NOR TCAM architecture, match lines are pre-charged high and evaluate low to indicate a mismatch. The majority of comparisons yield a mismatch, and therefore, the dynamic NOR has an increased power consumption as a result of switching from high to low for indicating a mismatch. Furthermore, the dynamic NOR has a complex timing control because the pre-charge signal is used by each match line in each clock cycle.
FIG. 2 illustrates a conventional dynamic NOR TCAM 200. As illustrated in FIG. 2, the dynamic NOR TCAM 200 includes key cells Key0-Keyn−1 and mask cells Mask0-Maskn−1. Typically, a NOR TCAM, such as the NOR TCAM 200 of FIG. 2, may have sixteen key and mask cells. Data is input via search lines (SL0-SLn−1 and SL0#-SLn−1#). The data is compared to the values stored in the key cells Key0-Keyn−1 and mask cells Mask0-Maskn−1. The match line MLNOR is pre-charged high via the pre-charge line PRE# from a pull-up transistor 202. The match line MLNOR will evaluate low when there is a mismatch between the data input via one of the search lines (SL0-SLn−1 and SL0#-SLn−1#) and the data stored in one of the cells Key0-Keyn−1 Mask0-Maskn−1. The match line remains high when the values of all of the cells Key0-Keyn−1 Mask0-Maskn−1 match the input data.
The structure of the key cells Key0-Keyn−1 is illustrated in the expanded key cell 220 and the structure of the mask cells Mask0-Maskn−1 is illustrated in the expanded mask cell 222. As illustrated in the expanded key cell 220, the key cells Key0-Keyn−1 are implemented via an SRAM cell. During a compare operation, the key bar K# is ANDed with the search line SL. The key cells Key0-Keyn−1 include a bit line BLK, a bit line bar BLK#, and a word line WLK.
As illustrated in the expanded mask cell 222, the mask cells Mask0-Maskn−1 are implemented via a SRAM cell. During a comparison operation, the mask bar M# is ANDed with the search line bar SL#. The mask cells Mask0-Maskn−1 include a bit line BLM, a bit line bar BLM#, and a word line WLM.
TABLE 1 is a truth table for the dynamic NOR TCAM. TABLE 1 shows the value of the match line based on the values of the mask cells (M), key cells (K), and the search lines (SL and SL#). It should be noted that the state refers to the state of a storage element (key cell and mask cell). The state is 0 when the key bit has a value of 0, the state is 1 when the key bit has a value of 1, and the state is X when both the mask bit and the key bit are 1. The state of X refers to a mask state in which there is neither a match nor a mismatch, rather, there is no comparison between the value of the search line and the values of the mask cell and key cell. Thus, the match line always indicates a match.
TABLE 1SearchMask BitKey BitSearchLine BarMatch LineState(M)(K)Line (SL)(SL#)(MLNOR)010011010100101010101101X11XX1—00——NotAllowed
As shown in TABLE 1, the match line will be 0 (low) and indicate a mismatch when the key bit and search line have different values. Likewise, the match line will be 0 and indicate a mismatch when both the mask bit and search line bar have different values. That is, when the key bit is 0 (e.g., key bit bar (K#) is 1) and the search line is 1 or when the mask bit is 0 (e.g., mask bit bar (M#) is 1) and the search line bar is 1, a pull down transistor will be activated to pull the match line to low. Moreover, the match line will be 1 (high) and indicate a match when the key bit and search line have the same values. Likewise, the match line will be 1 and indicate a match when both the mask bit and search line bar have the same values. Furthermore, when both the mask bit and key bit are 1, the state is X. That is, the match line will remain high and indicate a match regardless of the value of the search line.
As discussed above, in a dynamic NOR TCAM, the match lines and search lines are pre-charged high at the beginning of every cycle and the match lines evaluate low to indicate a mismatch. The majority of comparisons of the cells in a TCAM yield a mismatch. Thus, the power consumption of the dynamic NOR TCAM is increased as a result of the switching from high to low when indicating a mismatch. In some cases, match lines may be pre-discharged low to reduce the power consumption. Still, even when then match lines are pre-discharged, a pre-charge operation charges the match line at the beginning of every cycle. Accordingly, the pre-charging of the match line leads to an increase in power consumption and additionally control circuitry.
In a dynamic NAND TCAM architecture, the match lines are pre-charged high and evaluate low to indicate a match. That is, a pre-charge signal is used for each match line during every cycle to set the match lines to high. Depending on the status of the mask cell or key cell, the match line may be pulled low or remain high. Each intermediate match line is associated with a mask cell and a key cell. Furthermore, each key cell further includes XNOR logic. The dynamic NAND TCAM uses a serial operation. Thus, an intermediate match line (n−1) may discharge (e.g., compare with the value of the search line) when the previous intermediate match line (n−2) was pulled low to indicate a match. That is, the operation continues from one intermediate match line (n−2) to a subsequent intermediate match line (n−1) when there is a match and stops progressing through the intermediate match lines when there is a mismatch.
The power consumption of the conventional dynamic NAND TCAM during a match line evaluation may be less than the power consumption of the conventional dynamic NOR TCAM because of the serial operation. Still, the conventional dynamic NAND TCAM may be undesirable because of errors resulting from charge-sharing.
FIG. 3 illustrates a conventional dynamic NAND TCAM 300. As illustrated in FIG. 3, the dynamic NAND architecture 300 includes a match line output MLNAND charged by a pre-charge line PRE# from a pull-up transistor 310. The match line output MLNAND is connected to a series of intermediate match lines ML0-MLn−1. Each of the intermediate match lines ML0-MLn−1 is coupled to a mask cell Mask0-Maskn−1 and a key cell Key0-Keyn−1 via transistors connected in parallel (e.g., transmission gate). The transistors connected in parallel include a key NMOS transistor 303 coupled to a key cell Key0-Keyn−1 and a mask NMOS transistor 304 coupled to a mask cell Mask0-Maskn−1.
The content of the mask cells Mask0-Maskn−1 is illustrated in an expanded mask cell 333. As shown in the expanded mask cell 333, mask cells Mask0-Maskn−1 are SRAM cells including a mask value M, a mask value bar M#, a mask word line WLM, a mask bit line BLM, and a mask bit line bar BLM#. The content of the key cells Key0-Keyn−1 is illustrated in an expanded key cell 330. As shown in the expanded key cell 330, the key cells Key0-Keyn−1 are SRAM cells with XNOR logic. The key cells Key0-Keyn−1 further include a search line SL, a search line bar SL#, a key bit line BLK, a key bit line bar BLK#, a key value K, a key bar value K#, a key write line WLK, and an output line XNOR.
TABLE 2MaskKeySearchBitBitLineMLi → MLi+1State(M)(K)(SL)XNORPropagationMLNAND01001ON0/101010OFFFloating11100OFFFloating11111ON0/1X0XXXON0/1
In a dynamic NAND TCAM architecture, the MLNAND is pre-charged high and evaluates low to indicate a match. Depending on the status of the mask cell or key cell, the MLNAND may be pulled low or remain high. Each intermediate match line (ML0-MLn−1) is associated with a mask cell and a key cell. The dynamic NAND TCAM uses a serial operation, therefore, an intermediate match line MLi may be pulled low (depending on the values of the Key and Mask cells) if the previous intermediate match line MLi−1 indicates a match. That is, a zero (low intermediate match line) propagates from one intermediate match line MLi to a subsequent intermediate match line MLi+1 when there is a match. Furthermore, the zero stops progressing through the intermediate match lines when there is a mismatch. Accordingly, the propagation of a zero from a current intermediate match line MLi to a subsequent intermediate match line MLi+1 also specifies that all of the previous match lines indicated a match.
Because the intermediate match lines are serially connected, the state of the match line output MLNAND is unknown until all the intermediate match lines are evaluated or until a mismatch is determined Therefore, as shown in TABLE 2, the match line output MLNAND will be either 0/1 when a mismatch has not yet been determined.
When a current intermediate match line MLi evaluates low to indicate a match, the dynamic NAND TCAM propagates this low value from the current intermediate match line MLi to a subsequent intermediate match line MLi+1. The propagation from the current intermediate match line MLi to a subsequent intermediate MLi+1 is shown as the ON switch in TABLE 2. Furthermore, the match line output MLNAND is either 0/1, because a mismatch has not yet been determined.
When a current intermediate match line MLi remains high to indicate a mismatch, the dynamic NAND TCAM does not propagate from the current intermediate match line MLi to a subsequent intermediate MLi−1. Thus, TABLE 2 indicates the propagation as OFF when a current intermediate match line MLi indicates a mismatch. More specifically, the operations of subsequent intermediate match lines stop when the current intermediate match line indicates a mismatch.
In TABLE 2 the value for XNOR represents the value of the output from key cell. A mismatch is indicated when the XNOR is 0. The current intermediate match line, such as MLi, remains high because of the mismatch. A match is indicated when the XNOR is 1, and the current intermediate match line, such as MLi, is pulled low when there is a match (if intermediate match lines to the left of the current intermediate match line have also been pulled low). Finally, in TABLE 2, the state refers to the state of a storage element (key cell and mask cell). The state is 0 when the key cell has a value of 0; the state is 1 when the key cell has a value of 1; and the state is X when the mask cell is 0. That is, for the state of X, when the mask cell is 0, the mask NMOS transistor 304 is enabled regardless of the XNOR value. More specifically, the state of X refers to a mask state in which there is neither a match nor a mismatch, rather, there is no comparison between the value of the search line and the values key cell.
In some cases, a conventional dynamic NAND TCAM with a deep NMOS stack may fail due to charge sharing. FIG. 4 illustrates an example of a dynamic NAND with a deep NMOS stack. During a pre-charge cycle all intermediate match line junction capacitances CJ0-CJ3 may be discharged to low. During an evaluate cycle, MLNAND is pre-charged high and the dynamic node capacitance CML is exposed to one or more of the intermediate match line junction capacitances CJ and shares the charge with the one or more intermediate match line junction capacitances CJ. As a result of the charge sharing, the voltage level of the match line output MLNAND may fall below a threshold voltage of the next inverter and trigger a false operation.
The speed of a TCAM may increase with an increase in the depth of an NMOS stack. Still, the speed of the dynamic NAND is limited due to the aforementioned charge sharing failure. Accordingly, the dynamic NOR TCAM may perform at speeds greater than the speed of a dynamic NAND TCAM. In some cases, to mitigate failure resulting from charge sharing, the intermediate junction capacitances CJ may be pre-charged to a VDD-Vt voltage level, where VDD is a supply level and Vt is a threshold voltage. Still, pre-charging the intermediate junction capacitances may not be desirable due to an increased area and additional timing complexity. In other cases, to mitigate failure resulting from charge sharing, the search line may be dynamic and pre-charged high every cycle to propagate a VDD-Vt voltage level through the NMOS stack. Nonetheless, pre-charging the search line may not be desirable because it is a dynamic power solution and results in an increased delay.